Largest divisible subset

Time: O(N^2); Space: O(N); medium

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

Input: nums = [1,2,3]

Output: [1,2] or [1,3]

Example 2:

Input: nums = [1,2,4,8]

Output: [1,2,4,8]

class Solution1(object):
    """
    Time: O(N^2)
    Space: O(N)
    """
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []

        nums.sort()
        dp = [1] * len(nums)
        prev = [-1] * len(nums)
        largest_idx = 0
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if dp[i] < dp[j] + 1:
                        dp[i] = dp[j] + 1
                        prev[i] = j
            if dp[largest_idx] < dp[i]:
                largest_idx = i

        result = []
        i = largest_idx
        while i != -1:
            result.append(nums[i])
            i = prev[i]
        return result[::-1]

s = Solution1()

nums = [1,2,3]
assert s.largestDivisibleSubset(nums) == [1,2] or [1,3]

nums = [1,2,4,8]
assert s.largestDivisibleSubset(nums) == [1,2,4,8]

See also:

https://leetcode.com/problems/largest-divisible-subset

https://www.lintcode.com/problem/largest-divisible-subset/description